package sort;

/**
 * 时间复杂度是O（NlogN） 空间复杂度是O（1）
 * 堆排序  假设节点下标为i 那么他的父节点 则为 i-1/2 ，左孩子节点则为 2 * i + 1，右孩子节点下标为2 * i + 2
 * 堆结构就是用数组实现的完全二叉树的结构，优先级队列结构也是堆结构
 */
public class HeadSort {

    public static void main(String[] args) {
        int[] arr = {1,3,56,3,6,8,5,23};
        headsort(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }

    public static void headsort(int[] arr){
        if (arr==null || arr.length<2){
            return;
        }
        //先形成大根堆
//        for (int i = 0; i < arr.length; i++) {  //O(N)
//            heapInsert(arr,i); //O(logN)
//        }

        //这个方法也能形成大根堆 并且快一点。由底下进行heapify则可以形成局部的根堆，以此类推
        for (int i = arr.length - 1 ; i>= 0;i--){
            heapify(arr,i,arr.length);
        }
        int heapSize = arr.length;
        //断掉最后一位，并交换剩下的最后一位与第0位，最后排序就是有序的了
        swap(arr,0,--heapSize);
        while (heapSize > 0){   //o(N)
            heapify(arr,0,heapSize);  //O(logN)
            swap(arr,0,--heapSize);
        }
    }

    //index插入向上移动
    private static void heapInsert(int[] arr, int index) {
        //判断在完全二叉树中，数组中新插入的节点，大于自己的父节点嘛，大于的话就进行交换
        while (arr[index] > arr[(index-1) / 2]){
            swap(arr,index,(index-1) / 2);
            index = (index-1)/2;
        }
    }

    //inde修改往下移动
    private static void heapify(int[] arr, int index, int heapSize) {
        int left = index * 2 +1;  //左孩子下标
        while (left < heapSize){  //下方还有孩子
            //判断是否有右孩子，并把最大孩子的下标赋值给largest
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 :left ;
            //判断最大孩子和父的哪个值大，并把下标给到largest
            largest = arr[largest] > arr[index] ? largest : index ;
            if (largest == index){  //经过重重pk，还是原本index下标的值大
                break;
            }
            //交换
            swap(arr,index,largest);
            index = largest;
            left = index * 2 +1;
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
